package uestc.lj.leetcode.day1;

import java.util.*;

/**
 * @Author:Crazlee
 * @Date:2021/11/24
 */
public class LeetCode {
	//定义双向链表节点类
	class ListNode {
		//成员变量
		int key;
		int value;
		ListNode next;
		ListNode prev;

		//构造方法
		public ListNode(int key, int value) {
			this.key = key;
			this.value = value;
		}

	}

	class LRUCache {
		//虚拟头结点
		private ListNode head;
		//虚拟尾节点
		private ListNode tail;
		//哈希表的键是缓存的键
		private Map<Integer, ListNode> numToNode;
		private int capacity;

		public LRUCache(int capacity) {
			numToNode = new HashMap<>();

			//初始化双向链表
			head = new ListNode(-1, -1);
			tail = new ListNode(-1, -1);
			head.next = tail;
			tail.prev = head;

			this.capacity = capacity;
		}

		public int get(int key) {
			if (!numToNode.containsKey(key)) {
				return -1;
			}
			ListNode node = numToNode.get(key);
			moveToTail(node, node.value);
			return node.value;
		}

		public void put(int key, int value) {
			if (numToNode.containsKey(key)) {
				//哈希表包含键
				moveToTail(numToNode.get(key), value);
			} else {
				//哈希表不包含键
				if (numToNode.size() == capacity) {
					//缓存达到容量上限
					ListNode node = head.next;
					//双向链表删除最近最少使用节点
					deleteNode(node);
					//哈希表（缓存）删除最近最少使用节点
					numToNode.remove(node.key);
				}

				//缓存未达到容量上限
				ListNode node = new ListNode(key, value);
				//双向链表插入节点
				insertToTail(node);
				//哈希表（缓存）插入节点
				numToNode.put(key, node);

			}

		}

		//将节点移动到双向链表的尾部
		private void moveToTail(ListNode node, int newValue) {
			deleteNode(node);
			//如果是插入一个键值对，键相同，值不同，要将节点值更新移动要双向链表结尾
			node.value = newValue;
			insertToTail(node);
		}

		//删除节点
		private void deleteNode(ListNode node) {
			node.prev.next = node.next;
			node.next.prev = node.prev;
		}

		//将节点插入到双向链表的尾部
		private void insertToTail(ListNode node) {
			tail.prev.next = node;
			node.prev = tail.prev;
			node.next = tail;
			tail.prev = node;
		}
	}

	public class Node {
		public int val;
		public Node left;
		public Node right;
		public Node next;

		public Node() {
		}

		public Node(int _val) {
			val = _val;
		}

		public Node(int _val, Node _left, Node _right, Node _next) {
			val = _val;
			left = _left;
			right = _right;
			next = _next;
		}
	}

	public Node connect(Node root) {
		if (root == null) {
			return root;
		}

		Queue<Node> queue = new LinkedList<>();
		queue.add(root);

		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				Node node = queue.poll();
				if (i < size - 1) {
					node.next = queue.peek();
				}
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
		}
		return root;
	}

	public int rob(int[] nums) {
		int length = nums.length;
		if (length < 3) {
			return Arrays.stream(nums).max().getAsInt();
		}
		return Math.max(dfs(nums, 0, length - 1), dfs(nums, 1, length));
	}

	private int dfs(int[] nums, int leftIndex, int rightIndex) {
		int length = nums.length;
		int[] dp = new int[length + 1];
		dp[leftIndex] = 0;
		dp[leftIndex + 1] += nums[leftIndex];
		for (int i = leftIndex + 2; i <= rightIndex; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
		}
		return dp[rightIndex];
	}

	public int minCostClimbingStairs(int[] cost) {
		int length = cost.length;
		int[] dp = new int[length + 1];
		dp[0] = dp[1] = 0;
		for (int i = 2; i <= length; i++) {
			dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
		}
		return dp[length];
	}

	public int scheduleCourse(int[][] courses) {
		//优先队列，按照课程的截止时间升序排序
		PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		});
		int total = 0;
		for (int[] cours : courses) {
			int duration = cours[0];
			int deadline = cours[1];
			if (total + duration < deadline) {
				total += duration;
				queue.offer(duration);
			}
			if (!queue.isEmpty() && queue.peek() > duration) {
				total -= queue.poll() - duration;
				queue.offer(duration);
			}
		}
		return queue.size();
	}

	public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
		dfsFloodFill(image, sr, sc, newColor, image[sr][sc]);
		return image;
	}

	private void dfsFloodFill(int[][] image, int sr, int sc, int newColor, int oldColor) {
		if (sr < 0 || sc < 0 || sr >= image.length || sc >= image[0].length) {
			return;
		}
		if (image[sr][sc] == oldColor && image[sr][sc] != newColor) {
			image[sr][sc] = newColor;
			dfsFloodFill(image, sr, sc + 1, newColor, oldColor);
			dfsFloodFill(image, sr, sc - 1, newColor, oldColor);
			dfsFloodFill(image, sr + 1, sc, newColor, oldColor);
			dfsFloodFill(image, sr - 1, sc, newColor, oldColor);
		}
	}

	public int findDuplicate(int[] nums) {
		int slow = 0, fast = 0;
		do {
			slow = nums[slow];
			fast = nums[nums[fast]];
		} while (slow != fast);
		slow = 0;
		while (slow != fast) {
			slow = nums[slow];
			fast = nums[fast];
		}
		return slow;
	}

	public int minCost(int[][] costs) {
		int row = costs.length;
		int[][] dp = new int[row][3];
		dp[0][0] = costs[0][0];
		dp[0][1] = costs[0][1];
		dp[0][2] = costs[0][2];
		for (int i = 1; i < row; i++) {
			dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
			dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
			dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2];
		}
		return Math.min(Math.min(dp[row - 1][0], dp[row - 1][1]), dp[row - 1][2]);
	}

	public int longestCommonSubsequence(String text1, String text2) {
		if (text1 == null || text2 == null || "".equals(text1) || "".equals(text2)) {
			return 0;
		}
		char[] chs1 = text1.toCharArray();
		char[] chs2 = text2.toCharArray();
		return dfslongestCommonSubsequence(chs1, chs2);
	}

	private int dfslongestCommonSubsequence(char[] chs1, char[] chs2) {
		int[][] dp = new int[chs1.length][chs2.length];
		dp[0][0] = chs1[0] == chs2[0] ? 1 : 0;
		for (int i = 1; i < chs1.length; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], chs1[i] == chs2[0] ? 1 : 0);
		}
		for (int i = 1; i < chs2.length; i++) {
			dp[0][i] = Math.max(dp[0][i - 1], chs1[0] == chs2[i] ? 1 : 0);
		}

		for (int i = 1; i < chs1.length; i++) {
			for (int j = 1; j < chs2.length; j++) {
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				if (chs1[i] == chs2[j]) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
				}
			}
		}
		return dp[chs1.length - 1][chs2.length - 1];
	}

	public int minCut(String s) {
		if (s == null || s.length() == 0) {
			return 0;
		}
		char[] chars = s.toCharArray();
		int length = chars.length;
		int[] dp = new int[length + 1];
		dp[length] = -1;

		boolean[][] p = new boolean[length][length];
		for (int i = length - 1; i >= 0; i++) {
			dp[i] = Integer.MAX_VALUE;
			for (int j = i; j < length; j++) {
				if (chars[i] == chars[j] && (j - i < 2 || p[i + 1][j - 1])) {
					p[i][j] = true;
					dp[i] = Math.min(dp[i], dp[j + 1] + 1);
				}
			}
		}
		return dp[0];
	}

	public int coinChange1(int[] coins, int amount) {
		if (coins == null || coins.length == 0) {
			return 0;
		}
		int[][] dp = new int[coins.length + 1][amount + 1];
		dp[coins.length][0] = 1;
		for (int i = 1; i <= amount; i++) {
			dp[coins.length][i] = 0;
		}
		for (int index = coins.length - 1; index >= 0; index--) {
			for (int rest = 0; rest <= amount; rest++) {
				int ways = 0;
				for (int zhang = 0; coins[index] * zhang <= rest; zhang++) {
					ways += dp[index + 1][rest - coins[index] * zhang];
				}
				dp[index][rest] = ways;
			}
		}

		return dp[0][amount];
	}

	public int countBattleships(char[][] board) {
		int row = board.length;
		int col = board[0].length;
		int ans = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (board[i][j] == 'X') {
					if (i > 0 && board[i - 1][j] == 'X') {
						continue;
					}
					if (j > 0 && board[i][j - 1] == 'X') {
						continue;
					}
					ans++;
				}
			}
		}
		return ans;
	}

	public int[] sortArray(int[] nums) {
		quickSort(nums, 0, nums.length - 1);
		return nums;
	}

	private void quickSort(int[] nums, int l, int r) {
		if (l < r) {
			int pos = randomPartition(nums, l, r);
			quickSort(nums, l, pos - 1);
			quickSort(nums, pos + 1, r);
		}
	}

	private int randomPartition(int[] nums, int l, int r) {
		int pos = new Random().nextInt(r - l + 1) + 1;
		swap(nums, r, pos);
		return partition(nums, l, r);
	}

	private int partition(int[] nums, int l, int r) {
		int povit = nums[r];
		int i = l - 1;
		for (int j = l; j <= r - 1; j++) {
			if (nums[j] < povit) {
				i = i + 1;
				swap(nums, i, j);
			}
		}
		swap(nums, i + 1, r);
		return i + 1;
	}

	private void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

	int ans = 0;

	public int findTargetSumWays(int[] nums, int target) {
		dfsFindTargetSumWays(nums, target, 0, 0);
		return ans;
	}

	private void dfsFindTargetSumWays(int[] nums, int target, int index, int sum) {
		if (index == nums.length) {
			if (sum == target) {
				ans++;
			}
		} else {
			dfsFindTargetSumWays(nums, target, index + 1, sum + nums[index]);
			dfsFindTargetSumWays(nums, target, index + 1, sum - nums[index]);
		}
	}

	public int maxCoins(int[] nums) {
		if (nums == null || nums.length == 0) {
			return 0;
		}
		LinkedList<Integer> arr = new LinkedList<>();
		for (int num : nums) {
			arr.add(num);
		}
		return dfsmaxCoins(arr);
	}

	private int dfsmaxCoins(LinkedList<Integer> arr) {
		if (arr.size() == 0) {
			return 0;
		}
		int size = arr.size();
		int res = 0;
		for (int i = 0; i < size; i++) {
			int left = (i - 1 >= 0) ? arr.get(i - 1) : 1;
			int right = (i + 1 < size) ? arr.get(i + 1) : 1;
			int total = left * right * arr.get(i);
			int temp = arr.remove(i);
			total += dfsmaxCoins(arr);
			res = Math.max(res, total);
			arr.add(i, temp);
		}
		return res;
	}

	public int minimumTotal(List<List<Integer>> triangle) {
		int n = triangle.size();
		int[][] dp = new int[n][n];
		dp[0][0] = triangle.get(0).get(0);

		for (int i = 1; i < n; i++) {
			dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
			for (int j = 1; j < i; j++) {
				dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
			}
			dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
		}
		int min = dp[n - 1][0];
		for (int i = 1; i < n; i++) {
			min = Math.min(min, dp[n - 1][i]);
		}
		return min;
	}

	public List<String> generateParenthesis(int n) {
		List<String> result = new ArrayList<>();
		if (n == 0) {
			return result;
		}
		dfsGeneratrParenthesis("", n, n, result);
		return result;
	}

	private void dfsGeneratrParenthesis(String curString, int leftNum, int rightNum, List<String> res) {
		if (leftNum == 0 && rightNum == 0) {
			res.add(curString);
			return;
		}
		if (leftNum > rightNum) {
			return;
		}
		if (leftNum > 0) {
			dfsGeneratrParenthesis(curString + "(", leftNum - 1, rightNum, res);
		}
		if (rightNum > 0) {
			dfsGeneratrParenthesis(curString + ")", leftNum, rightNum - 1, res);
		}
	}

	public int combinationSum4(int[] nums, int target) {
		int[] dp = new int[target + 1];
		dp[0] = 1;
		for (int i = 1; i <= target; i++) {
			for (int num : nums) {
				if (num <= i) {
					dp[i] += dp[i - num];
				}
			}
		}
		return dp[target];
	}

	public int missingNumber(int[] nums) {
		int xor = 0;
		int n = nums.length;
		for (int i = 0; i < n; i++) {
			xor ^= nums[i];
		}
		for (int i = 0; i <= n; i++) {
			xor ^= i;
		}
		return xor;
	}

	public int maxAreaOfIsland(int[][] grid) {
		if (grid == null || grid.length == 0) {
			return 0;
		}
		int row = grid.length;
		int col = grid[0].length;
		int res = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (grid[i][j] == 1) {
					res++;
					dfsMaxAreaOfIsland(grid, i, j, row, col);
				}
			}
		}
		return res;
	}

	private void dfsMaxAreaOfIsland(int[][] grid, int i, int j, int row, int col) {
		if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] != 1) {
			return;
		}
		grid[i][j] = 2;
		dfsMaxAreaOfIsland(grid, i - 1, j, row, col);
		dfsMaxAreaOfIsland(grid, i + 1, j, row, col);
		dfsMaxAreaOfIsland(grid, i, j - 1, row, col);
		dfsMaxAreaOfIsland(grid, i, j + 1, row, col);
	}

	public int[] countBits(int n) {
		int[] bits = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			bits[i] = countOnes(i);
		}
		return bits;
	}

	private int countOnes(int n) {
		int ones = 0;
		while (n > 0) {
			n &= (n - 1);
			ones++;
		}
		return ones;
	}

	List<List<Integer>> result = new ArrayList<>();
	Deque<Integer> stack = new ArrayDeque<>();

	public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
		stack.offerLast(0);
		dfsAllPathsSourceTarget(graph, 0, graph.length - 1);
		return result;
	}

	private void dfsAllPathsSourceTarget(int[][] graph, int x, int n) {
		if (x == n) {
			result.add(new ArrayList<>(stack));
			return;
		}
		for (int y : graph[x]) {
			stack.offerLast(y);
			dfsAllPathsSourceTarget(graph, y, n);
			stack.pollLast();
		}
	}

	public int longestIncreasingPath(int[][] matrix) {
		int row = matrix.length;
		int col = matrix[0].length;
		int[][] mark = new int[row][col];
		int res = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				res = Math.max(res, dfsLongestIncreasingPath(mark, i, j, -1, mark));
			}
		}
		return res;
	}

	private int dfsLongestIncreasingPath(int[][] matrix, int i, int j, int pre, int[][] mark) {
		int row = matrix.length;
		int col = matrix[0].length;
		if (i < 0 || j < 0 || i >= row || j >= col) {
			return 0;
		}
		if (matrix[i][j] <= pre) {
			return 0;
		}
		if (mark[i][j] != 0) {
			return mark[i][j];
		}
		mark[i][j] = 1 + Math.max(dfsLongestIncreasingPath(matrix, i + 1, j, matrix[i][j], mark),
				Math.max(dfsLongestIncreasingPath(matrix, i, j + 1, matrix[i][j], mark),
						Math.max(dfsLongestIncreasingPath(matrix, i - 1, j, matrix[i][j], mark),
								dfsLongestIncreasingPath(matrix, i, j - 1, matrix[i][j], mark))));
		return mark[i][j];
	}
}

